package th.retrofit.lib;

/**
 * 给定一个m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
 *
 * 进阶：
 *
 * 一个直观的解决方案是使用 O(mn)的额外空间，但这并不是一个好的解决方案。
 * 一个简单的改进方案是使用 O(m+n) 的额外空间，但这仍然不是最好的解决方案。
 * 你能想出一个仅使用常量空间的解决方案吗？
 *
 */
public class Solution73 {

    // 找到第一个为0的数据,假设为matrix[row][column],将该数据所在的行和列标记为选中行和选中列,
    // 如果出现其它行列数据为0的情况,如matrix[i][j] = 0,则将对应选中行列所在位置的值设计为0,
    // 即令matrix[i][column] = 0, matrix[row][j] = 0.
    public void setZeroes(int[][] matrix) {
        int row = -1, column = -1;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    if (row == -1) {
                        row = i;
                        column = j;
                    } else {
                        matrix[row][j] = 0;
                        matrix[i][column] = 0;
                    }
                }
            }
        }
        if (row == -1) return;
        // 将除了选定行之外的所有行置为0.如果不降选定行排除在外,则会导致该行全为0,在遍历将列置为0的时候引起错误,将不该为0的列置为0.
        for (int i = 0; i < matrix.length; i++) {
            if (i == row) continue;
            if (matrix[i][column] == 0) {
                for (int j = 0; j < matrix[0].length; j++) {
                    matrix[i][j] = 0;
                }
            }
        }
        //将列置为0,同时将选中行的数据置为0
        for (int i = 0; i < matrix[0].length; i++) {
            if (matrix[row][i] == 0) {
                for (int j = 0; j < matrix.length; j++) {
                    matrix[j][i] = 0;
                }
            } else {
                matrix[row][i] = 0;
            }
        }
    }

    public static void main(String[] args) {
//        int[][] matrix = new int[][]{{0,1,2,0},{3,4,5,2},{1,3,1,5}};
        int[][] matrix = new int[][]{{1}};
        new Solution73().setZeroes(matrix);
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                System.out.print(matrix[i][j]);
                System.out.print(", ");
            }
            System.out.println();
        }
    }

}
